//huffman.cpp

#include <stdio.h>
#include "huffman.h"


//---HuffItem
HuffItem::HuffItem(short _value, int _rate)
{
	zero=NULL;
	one=NULL;
	value=_value;
	rate=_rate;
	for(int i=0; i<257; ++i)
		code[i]=0;
	bitsCount=0;
}

Huffman::Huffman()
{
	clear();
}
void Huffman::clear()
{
	for(int i=0; i<256; ++i)
	{
		tableCounter[i]=0;
		cTable[i]=i;
	}
}
int Huffman::decompress(FILE* fileIn, FILE* fileOut)
{
	BitStream bitFileOut, bitFileIn;
	if((bitFileOut.open(fileOut, 'w'))==0)
		return 0;	
	if((bitFileIn.open(fileIn, 'r'))==0)
		return 0;

	listCounter=bitFileIn.get(9);
	treeCounter=listCounter;
	list= new HuffItem*[listCounter];
	tree= new HuffItem*[listCounter];

	{
		short temp;
		for(int i=0; i<listCounter; ++i)
		{
			temp=bitFileIn.get(9);
			list[i]= new HuffItem(temp,0);
			list[i]->bitsCount=bitFileIn.get(7);
		}
	}
	tree[0] = new HuffItem(0, 0);
	treeCounter=0;
	restoreTree(tree[0],1);

	int readnByte;
	for(long bytesCounter=0;;++bytesCounter)
	{
		//printf("\n--- %dlc  %d %d   %d+%d<%d || %d>%d(%d)",listCounter, trashInfoBytes, trashInfoBits, bitWork->bytewrite.bytestaken, modOfByte, shortbytesreadn, bitsTakenInLast2Bytes ,trueBitsTaken,bitWork->bytewrite.bitstaken);
		readnByte=getSymbol(bitFileIn,tree[0]);
		if(readnByte==256 || readnByte==-1)
			break;
		bitFileOut.put(readnByte,8);
			//printf("\n %c  %d+%d<%d || %d>%d(%d)", bytesBuffer[bytesTakeninBuffer], bitWork->bytewrite.bytestaken, modOfByte, shortbytesreadn, bitsTakenInLast2Bytes ,trueBitsTaken,bitWork->bytewrite.bitstaken);
	}

	//destr
	deleteTree(tree[0]);
	delete[] tree;
	tree=NULL;
	for(int i=0; i<listCounter; ++i)
		delete list[i];
	delete[] list;
	list=NULL;
	return 1;
}
int Huffman::getSymbol(BitStream& bs,HuffItem* mark)
{
	if(mark->zero!=NULL && mark->one!=NULL)
	{
		int value=bs.get(1);
		if(value==-1)
			return -1;
		if(value)
			return getSymbol(bs, mark->one);
		else
			return getSymbol(bs, mark->zero);
	}
	else
	{
		//printf("%c",mark->value);
		return mark->value;
	}
}
int Huffman::getRate(FILE* file)
{
	BitStream bitFile;
	if((bitFile.open(file, 'r'))==0)
		return 0;	
	int readnbyte;
	while(1)
	{
		readnbyte=bitFile.get(8);
		if(readnbyte==-1)
			break;
		++tableCounter[readnbyte];
	}	
	bitFile.close();
	return 1;
}
int Huffman::compress(FILE* fileIn, FILE* fileOut)
{
	BitStream bitFileOut,bitFileIn;
	if((bitFileOut.open(fileOut, 'w'))==0)
		return 0;	
	//if((bitFileIn.open(fileIn, 'r'))==0)
		//return 0;	

	getRate(fileIn);

	//bitFileIn.close();
	fseek(fileIn,0,SEEK_SET);
	if((bitFileIn.open(fileIn,'r'))==0)
		return 0;
	
	sortTable();
	
	
	for(listCounter=255; tableCounter[listCounter]==0; --listCounter);
	listCounter+=2;
	tableCounter[listCounter]=1; //adding EOF
	

	treeCounter=listCounter;
	list= new HuffItem*[listCounter];
	tree= new HuffItem*[listCounter];
	for(int i=0; i<listCounter; ++i)
	{
		if(i!=listCounter-1)
			list[i]= new HuffItem(cTable[i], tableCounter[i]);
		else
			list[i]= new HuffItem(256, tableCounter[i]); //EOF
		tree[i]=list[i];
	}
	makeTree();
	makeCodes(tree[0],0,0);
	
	treeCounter=0;
	resortList(tree[0]);

	writeHeader(bitFileOut);
	int readnbyte;
	while(1)
	{
		readnbyte=bitFileIn.get(8);
		if(readnbyte==-1)
			break;
		for(int j=0; j<listCounter; ++j)
		{
			if(readnbyte==list[j]->value)
			{
				for(int i=0; i<list[j]->bitsCount; ++i)
					bitFileOut.put(list[j]->code[i],1);
			}
		}
	}
	int EOFindex;
	for(EOFindex=0;list[EOFindex]->value!=256; ++EOFindex);
	for(int i=0; i<list[EOFindex]->bitsCount; ++i) //putting EOF
		bitFileOut.put(list[EOFindex]->code[i],1);

	//destr;
	deleteTree(tree[0]);
	delete[] tree;
	tree=NULL;
	for(int i=0; i<listCounter; ++i)
		delete list[i];
	delete[] list;
	list=NULL;
	return 1;
}
long Huffman::calcWeight()
{
	//printf("\n 4 BITS | BITS TAKEN IN THE LAST 2 BYTES - %d",calcBitsInLastByte());
	//printf("\n 8 BITS | symbolS COUNT - %d",listCounter);
	//printf("\n 8 BITS * symbolS COUNT =  %d | ALL symbolS",8*listCounter);
	//printf("\n 7 BITS * symbolS LVL =  %d | symbol'S LVL",7*listCounter);
	long res=0;
	for(int i=0; i<listCounter;++i)
		res=res+list[i]->rate*list[i]->bitsCount;
	//printf("\n %d BITS | huffMAN CODES", res);
	//printf("\n %d BITS | TOTAL", res+15*listCounter+12);
	//printf("\n %d BYTES | TOTAL", (res+15*listCounter+12)/8);
	return ((res+15*listCounter+12)/8); 
}
void Huffman::writeHeader(BitStream& bs)
{	
	bs.put(listCounter,9);
	for(int i=0; i<listCounter; ++i)
	{
		bs.put(list[i]->value,9);
		bs.put(list[i]->bitsCount,7);
	}
}
int Huffman::calcBitsInLastByte()
{
	int i;
	long res=0;
	for(i=0; i<listCounter;++i)
		res=res+list[i]->rate*list[i]->bitsCount;
	res=15*listCounter+12+res;
	res=res%8;
	return res;
}
void Huffman::deleteTree(HuffItem* mark)
{
	if(mark->zero==NULL)
		return;
	deleteTree(mark->zero);
	deleteTree(mark->one);
	delete mark;

}
void Huffman::resortList(HuffItem* mark)
{
	if(mark->zero==NULL)
	{
		list[treeCounter]=mark;
		++treeCounter;
		return;
	}

	resortList(mark->zero);
	resortList(mark->one);
}
int Huffman::makeCodes(HuffItem* mark, unchar code, int bitsCount)
{
	if(mark->zero==NULL && mark->one==NULL)
	{
		//CurrCode[bitsCount]=code;
		for(int i=0; i<bitsCount; ++i)
			mark->code[i]=CurrCode[/*bitsCount*/i];
		mark->bitsCount=bitsCount;
		//CurrCode[bitsCount]=0;	
		return 0;
	}
	CurrCode[bitsCount]=1;
	makeCodes(mark->one, 1, bitsCount+1);
	CurrCode[bitsCount]=0;	
	makeCodes(mark->zero, 0, bitsCount+1);
	return 1;
}
void Huffman::restoreTreeChecker(HuffItem* mark, int depth)
{
	if(depth==list[treeCounter]->bitsCount)
	{
		if(mark->zero==NULL)
		{
			mark->zero=list[treeCounter];
			++treeCounter;
		}
		else if(mark->one==NULL)
		{
			mark->one=list[treeCounter];
			++treeCounter;
		}
	}
}
void Huffman::restoreTree(HuffItem* mark, int depth)
{
	restoreTreeChecker(mark, depth);

	if(mark->zero==NULL)
	{
		mark->zero = new HuffItem(0,0);
		restoreTree(mark->zero, depth+1);
	}

	restoreTreeChecker(mark, depth);

	if(mark->one==NULL)
	{
		mark->one = new HuffItem(0,0);
		restoreTree(mark->one, depth+1);
	}
}
void Huffman::makeTree()
{
	HuffItem* temp;
	for(;treeCounter>1;)
	{
		temp=new HuffItem(0,0);
		temp->zero=tree[treeCounter-1];
		temp->one=tree[treeCounter-2];
		temp->rate=temp->one->rate+temp->zero->rate;
//		printf("\n? [%c]%d=[%c]%d+[%c]%d", temp->value,temp->rate, temp->one->value,temp->one->rate, temp->zero->value,temp->zero->rate);
		--treeCounter;
		tree[treeCounter-1]=temp;
		sortTree();
	}
}
void Huffman::sortTree()
{
	HuffItem* temp;
	for (int i=treeCounter-1; i>=0; --i)
	{
		if (tree[i]->rate<tree[i+1]->rate)
		{
			temp=tree[i];
			tree[i]=tree[i+1];
			tree[i+1]=temp;
		}
	}
}
void Huffman::sortTable()
{
	int temp=0;
	for (int i=0; i < 256; ++i)
	{
		for (int j=0; j < 256-i-1; ++j)
		{
			if (tableCounter[j] < tableCounter[j+1])
			{
				temp=tableCounter[j];
				tableCounter[j]=tableCounter[j+1];
				tableCounter[j+1]=temp;
				temp=cTable[j];
				cTable[j]=cTable[j+1];
				cTable[j+1]=temp;
			}
		}
	}
}
void Huffman::showTable()
{
	for(int i=0; i<listCounter; ++i)
	{
		printf("\n[%c][%d] [", list[i]->value, list[i]->value);
		for(int j=0; j<list[i]->bitsCount; ++j)
			printf("%d", list[i]->code[j]);
		printf("] %db - %d", list[i]->bitsCount,list[i]->rate);
	}
}
